{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Odd Even Linked List"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #linked-list"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: oddEvenList"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #奇偶链表"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给定单链表的头节点&nbsp;<code>head</code>&nbsp;，将所有索引为奇数的节点和索引为偶数的节点分别组合在一起，然后返回重新排序的列表。</p>\n",
    "\n",
    "<p><strong>第一个</strong>节点的索引被认为是 <strong>奇数</strong> ， <strong>第二个</strong>节点的索引为&nbsp;<strong>偶数</strong> ，以此类推。</p>\n",
    "\n",
    "<p>请注意，偶数组和奇数组内部的相对顺序应该与输入时保持一致。</p>\n",
    "\n",
    "<p>你必须在&nbsp;<code>O(1)</code>&nbsp;的额外空间复杂度和&nbsp;<code>O(n)</code>&nbsp;的时间复杂度下解决这个问题。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/10/oddeven-linked-list.jpg\" style=\"height: 123px; width: 300px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入: </strong>head = [1,2,3,4,5]\n",
    "<strong>输出:</strong>&nbsp;[1,3,5,2,4]</pre>\n",
    "\n",
    "<p><strong>示例 2:</strong></p>\n",
    "\n",
    "<p><img src=\"https://assets.leetcode.com/uploads/2021/03/10/oddeven2-linked-list.jpg\" style=\"height: 142px; width: 500px;\" /></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入:</strong> head = [2,1,3,5,6,4,7]\n",
    "<strong>输出:</strong> [2,3,6,7,1,5,4]</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示:</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n ==&nbsp;</code> 链表中的节点数</li>\n",
    "\t<li><code>0 &lt;= n &lt;= 10<sup>4</sup></code></li>\n",
    "\t<li><code>-10<sup>6</sup>&nbsp;&lt;= Node.val &lt;= 10<sup>6</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [odd-even-linked-list](https://leetcode.cn/problems/odd-even-linked-list/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [odd-even-linked-list](https://leetcode.cn/problems/odd-even-linked-list/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,4,5]', '[2,1,3,5,6,4,7]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head:\n",
    "            return head\n",
    "        odd = head\n",
    "        even = head.next\n",
    "        evenHead = even\n",
    "        while even and even.next:\n",
    "            odd.next = even.next\n",
    "            even.next = even.next.next\n",
    "            odd = odd.next\n",
    "            even = even.next\n",
    "        odd.next = evenHead\n",
    "        return head\n",
    "        \n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        odd_dh, even_dh = ListNode(0), ListNode(0)\n",
    "        odd_cur, even_cur = odd_dh, even_dh\n",
    "        \n",
    "        while head:\n",
    "            odd_cur.next = head\n",
    "            head = head.next\n",
    "            odd_cur = odd_cur.next\n",
    "            odd_cur.next = None\n",
    "            if head:\n",
    "                even_cur.next = head\n",
    "                head = head.next\n",
    "                even_cur = even_cur.next\n",
    "                even_cur.next = None\n",
    "        odd_cur.next = even_dh.next\n",
    "        return odd_dh.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        dummy_odd = ListNode(0)\n",
    "        dummy_even = ListNode(0)\n",
    "        parent_odd = dummy_odd\n",
    "        parent_even = dummy_even\n",
    "        node = head\n",
    "        isOdd = False\n",
    "        while node:\n",
    "            isOdd = not isOdd\n",
    "            if isOdd:\n",
    "                parent_odd.next = node\n",
    "                parent_odd = node\n",
    "            else:\n",
    "                parent_even.next = node\n",
    "                parent_even = node\n",
    "            node = node.next\n",
    "        parent_even.next = None\n",
    "        parent_odd.next = dummy_even.next\n",
    "        return dummy_odd.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        res=[]\n",
    "        while head:\n",
    "            res.append(head.val)\n",
    "            head=head.next\n",
    "        res=res[::2]+res[1::2]\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head):\n",
    "        \"\"\"\n",
    "        :type head: ListNode\n",
    "        :rtype: ListNode\n",
    "        \"\"\"\n",
    "        if not head or not head.next or not head.next.next:return head\n",
    "        target=head.next\n",
    "        index=1\n",
    "        temp=head\n",
    "        while temp.next:temp=temp.next\n",
    "        tail=temp\n",
    "        tail.next=head.next\n",
    "        head.next=head.next.next\n",
    "        tail=tail.next\n",
    "        tail.next=None\n",
    "        temp=head\n",
    "        target=tail\n",
    "        temp=head.next\n",
    "        while temp!=target and temp.next!=target:\n",
    "            print(temp.val if temp else None)\n",
    "            x=temp.next\n",
    "            temp.next=x.next\n",
    "            x.next=None\n",
    "            tail.next=x\n",
    "            tail=x\n",
    "            temp=temp.next\n",
    "        return head\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: 'ListNode') -> 'ListNode':\n",
    "        a = ListNode(0)\n",
    "        a1 = a\n",
    "        b = ListNode(0)\n",
    "        b1 = b\n",
    "        count = 1\n",
    "        while head:\n",
    "            if count%2 != 0:\n",
    "                a1.next = ListNode(head.val)\n",
    "                head = head.next\n",
    "                a1 = a1.next\n",
    "            else:\n",
    "                b1.next = ListNode(head.val)\n",
    "                head = head.next\n",
    "                b1 = b1.next\n",
    "            count +=1\n",
    "        a1.next = b.next\n",
    "        return a.next\n",
    "                \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None or head.next.next==None:\n",
    "            return head\n",
    "        odd=head\n",
    "        even=head.next\n",
    "        evenhead=head.next\n",
    "        while even!=None and even.next!=None :\n",
    "            odd.next=even.next\n",
    "            odd=odd.next\n",
    "            even.next=odd.next\n",
    "            even=even.next\n",
    "        odd.next=evenhead\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None or head.next.next==None:\n",
    "            return head\n",
    "        odd=head\n",
    "        even=head.next\n",
    "        evenhead=head.next\n",
    "        while even!=None and even.next!=None :\n",
    "            odd.next=even.next\n",
    "            odd=odd.next\n",
    "            even.next=odd.next\n",
    "            even=even.next\n",
    "        odd.next=evenhead\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next: return head\n",
    "        odd, even, even_head = head, head.next, head.next\n",
    "        while odd.next and odd.next.next and even.next and even.next.next:\n",
    "            odd.next, even.next = odd.next.next, even.next.next\n",
    "            odd, even = odd.next, even.next \n",
    "        \n",
    "        if even.next:\n",
    "            odd.next = odd.next.next\n",
    "            odd = odd.next\n",
    "\n",
    "        even.next = None\n",
    "        \n",
    "        odd.next = even_head\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if(not head or not head.next):\n",
    "            return head\n",
    "        odd = ListNode(0)\n",
    "        even = ListNode(0)\n",
    "        p1 = odd\n",
    "        p2 = even\n",
    "        p = head\n",
    "        while(p):\n",
    "            p1.next = p\n",
    "            p2.next = p.next\n",
    "            p1 = p1.next\n",
    "            p2 = p2.next\n",
    "            if(p.next):\n",
    "                p = p.next.next\n",
    "            else:\n",
    "                break\n",
    "        p1.next = even.next\n",
    "        return odd.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.next = None\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if head==None or head.next==None:return head\n",
    "        p=head\n",
    "        n=q=head.next\n",
    "        while q!=None:\n",
    "            p.next=q.next\n",
    "            if p.next==None:\n",
    "                break\n",
    "            q.next=p.next.next\n",
    "            p=p.next\n",
    "            q=q.next\n",
    "        p.next=n\n",
    "        return head\n",
    "            \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return None\n",
    "        odd = head\n",
    "        even = head.next\n",
    "        even_head = even\n",
    "        while even and even.next:\n",
    "            odd.next = even.next\n",
    "            odd = odd.next\n",
    "            even.next = odd.next\n",
    "            even = even.next\n",
    "        odd.next = even_head\n",
    "        return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "class ListNode:\n",
    "    def __init__(self, val=0, next=None):\n",
    "        self.val = val\n",
    "        self.next = next\n",
    "\n",
    "\n",
    "# 1、将原链表拆分成 奇链表 和 偶链表 两条链表；\n",
    "# 2、然后将 偶链表 的头部 拼接到 奇链表 的后面 即可。\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if not head: return head\n",
    "        odd = head\n",
    "        even = even_head = head.next\n",
    "        while odd.next and even.next:\n",
    "            odd.next = odd.next.next\n",
    "            even.next = even.next.next\n",
    "            odd, even = odd.next, even.next\n",
    "        odd.next = even_head  # 奇链表 尾部 链接 偶链表 的 头部\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        \n",
    "        # dummy = ListNode(0,head)\n",
    "        cur = head\n",
    "        evenHead = even = head.next\n",
    "\n",
    "        while even and even.next:\n",
    "            cur.next = even.next\n",
    "            even.next = cur.next.next\n",
    "            cur.next.next = evenHead\n",
    "\n",
    "            cur = cur.next\n",
    "            even = even.next\n",
    "\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        tmp1 = list1 = ListNode(0)\n",
    "        tmp2 = list2 = ListNode(0)\n",
    "        while head:\n",
    "            tmp1.next = head\n",
    "            tmp2.next = head.next\n",
    "            tmp1 = tmp1.next\n",
    "            tmp2 = tmp2.next\n",
    "            head = head.next.next if head.next else head.next\n",
    "        \n",
    "        tmp1.next = list2.next\n",
    "        return list1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        \n",
    "        p = head\n",
    "        num  = 1\n",
    "        p1 = one = ListNode(None)\n",
    "        p2 = two = ListNode(None)\n",
    "        while p:\n",
    "            node = ListNode(p.val)\n",
    "            if num % 2 == 1:\n",
    "                one.next = node\n",
    "                one = node\n",
    "            else:\n",
    "                two.next = node\n",
    "                two = node\n",
    "            p = p.next\n",
    "            num += 1\n",
    "        one.next = p2.next\n",
    "        return p1.next\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        l1 = ListNode(0)\n",
    "        l2 = ListNode(0)\n",
    "\n",
    "        tail1 = l1\n",
    "        tail2 = l2\n",
    "\n",
    "        i = 1\n",
    "        while head:\n",
    "            if i % 2 == 1:\n",
    "                node = ListNode(head.val)\n",
    "                tail1.next = node\n",
    "                tail1 = node \n",
    "            else:\n",
    "                node = ListNode(head.val)\n",
    "                tail2.next = node \n",
    "                tail2 = node \n",
    "            \n",
    "            i += 1\n",
    "            head = head.next\n",
    "        \n",
    "        tail1.next = None\n",
    "        tail2.next\n",
    "        \n",
    "        tail1.next = l2.next\n",
    "\n",
    "        return l1.next\n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "#class Solution:\n",
    " #   def oddEvenList(self, head: ListNode) -> ListNode:\n",
    " # Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: ListNode) -> ListNode:\n",
    "        if not head:\n",
    "            return head\n",
    "\n",
    "        odd,even=head,head.next\n",
    "        firstEven=even\n",
    "        # 1->2->3->4->5->null\n",
    "        while even and even.next:            \n",
    "            nexOdd=even.next\n",
    "            nexEven=nexOdd.next\n",
    "            # 1->3\n",
    "            odd.next=nexOdd\n",
    "            odd=nexOdd\n",
    "            # 2->4\n",
    "            even.next=nexEven\n",
    "            even=nexEven\n",
    "        # 5->2 \n",
    "        odd.next=firstEven\n",
    "        \n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if (head is None) or (head.next is None):\n",
    "            return head\n",
    "        count = 0\n",
    "        odd, even = ListNode(), ListNode()\n",
    "        odd_cur, even_cur = odd, even\n",
    "        while head:\n",
    "            count += 1\n",
    "            if count % 2:\n",
    "                odd_cur.next = head\n",
    "                odd_cur = odd_cur.next\n",
    "            else:\n",
    "                even_cur.next = head\n",
    "                even_cur = even_cur.next\n",
    "            head = head.next\n",
    "        odd_cur.next = even.next\n",
    "        even_cur.next = None\n",
    "        return odd.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        head1, head2 = ListNode(), ListNode()\n",
    "        cur1, cur2 = head1, head2\n",
    "        cur = head\n",
    "        index = 1\n",
    "        while cur:\n",
    "            if index % 2 != 0:\n",
    "                cur1.next = cur\n",
    "                cur1 = cur\n",
    "            else:\n",
    "                cur2.next = cur\n",
    "                cur2 = cur\n",
    "            cur = cur.next\n",
    "            index += 1\n",
    "        cur1.next = head2.next\n",
    "        cur2.next = None\n",
    "        return head1.next"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head is None or head.next is None:\n",
    "            return head\n",
    "        even = ListNode(-1)\n",
    "        ecur = even\n",
    "        ocur = head\n",
    "        cur = head.next\n",
    "        cnt = 0\n",
    "        while cur is not None:\n",
    "            if cnt % 2 == 0:\n",
    "                ecur.next = cur\n",
    "                ecur = ecur.next\n",
    "            else:\n",
    "                ocur.next = cur\n",
    "                ocur = ocur.next\n",
    "            cur = cur.next\n",
    "            cnt += 1\n",
    "        # first set even end to None\n",
    "        ecur.next = None\n",
    "        # finally concat\n",
    "        ocur.next = even.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next: return head\n",
    "        odd_head = head \n",
    "        even_head = head.next\n",
    "        even_copy = even_head\n",
    "        while even_head and even_head.next:\n",
    "            # print(odd_head.val,even_head.val)\n",
    "            odd_head.next = even_head.next\n",
    "            if even_head.next: even_head.next = even_head.next.next\n",
    "            odd_head = odd_head.next\n",
    "            even_head = even_head.next\n",
    "        odd_head.next = even_copy \n",
    "        return head\n",
    "        \n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        odd, even = ListNode(0, None), ListNode(0, None)\n",
    "        odd_cur, even_cur = odd, even\n",
    "        loop = head\n",
    "        n = 0\n",
    "        while loop:\n",
    "            if n % 2 == 0:\n",
    "                odd_cur.next = ListNode(loop.val, None)\n",
    "                odd_cur = odd_cur.next\n",
    "            else:\n",
    "                even_cur.next = ListNode(loop.val, None)\n",
    "                even_cur = even_cur.next\n",
    "            loop = loop.next\n",
    "            n += 1\n",
    "        odd_cur.next = even.next\n",
    "        \n",
    "        return odd.next\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if head == None:\n",
    "            return head\n",
    "        p=head.next\n",
    "        dummy=ListNode()\n",
    "        pre=dummy\n",
    "        while p is not None: \n",
    "            pre.next=ListNode(p.val)\n",
    "            pre=pre.next\n",
    "            p=p.next\n",
    "        p=head\n",
    "        pre=None\n",
    "        while p and p.next:\n",
    "            p.next=p.next.next\n",
    "            pre=p\n",
    "            p=p.next\n",
    "        q=dummy.next\n",
    "        while q and q.next:\n",
    "            q.next=q.next.next\n",
    "            q=q.next\n",
    "        if p == None:\n",
    "            pre.next=dummy.next\n",
    "        else:\n",
    "            p.next=dummy.next\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head: return head\n",
    "        odd = head\n",
    "        even_head = even = head.next\n",
    "        while odd.next and even.next:\n",
    "            odd.next = odd.next.next\n",
    "            even.next = even.next.next\n",
    "            odd = odd.next\n",
    "            even = even.next\n",
    "        odd.next = even_head\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for singly-linked list.\n",
    "# class ListNode:\n",
    "#     def __init__(self, val=0, next=None):\n",
    "#         self.val = val\n",
    "#         self.next = next\n",
    "class Solution:\n",
    "    def oddEvenList(self, head: Optional[ListNode]) -> Optional[ListNode]:\n",
    "        if not head or not head.next:\n",
    "            return head\n",
    "        odd = head \n",
    "        even = head.next \n",
    "        concated = even\n",
    "        while even and even.next:\n",
    "            odd.next = even.next\n",
    "            odd = odd.next \n",
    "\n",
    "            even.next = odd.next \n",
    "            even = even.next\n",
    "        odd.next = concated\n",
    "        return head\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
